{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Integer to Roman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: intToRoman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #整数转罗马数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>罗马数字包含以下七种字符： <code>I</code>， <code>V</code>， <code>X</code>， <code>L</code>，<code>C</code>，<code>D</code> 和 <code>M</code>。</p>\n",
    "\n",
    "<pre>\n",
    "<strong>字符</strong>          <strong>数值</strong>\n",
    "I             1\n",
    "V             5\n",
    "X             10\n",
    "L             50\n",
    "C             100\n",
    "D             500\n",
    "M             1000</pre>\n",
    "\n",
    "<p>例如， 罗马数字 2 写做 <code>II</code> ，即为两个并列的 1。12 写做 <code>XII</code> ，即为 <code>X</code> + <code>II</code> 。 27 写做  <code>XXVII</code>, 即为 <code>XX</code> + <code>V</code> + <code>II</code> 。</p>\n",
    "\n",
    "<p>通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 <code>IIII</code>，而是 <code>IV</code>。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 <code>IX</code>。这个特殊的规则只适用于以下六种情况：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>I</code> 可以放在 <code>V</code> (5) 和 <code>X</code> (10) 的左边，来表示 4 和 9。</li>\n",
    "\t<li><code>X</code> 可以放在 <code>L</code> (50) 和 <code>C</code> (100) 的左边，来表示 40 和 90。 </li>\n",
    "\t<li><code>C</code> 可以放在 <code>D</code> (500) 和 <code>M</code> (1000) 的左边，来表示 400 和 900。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数，将其转为罗马数字。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> num = 3\n",
    "<strong>输出:</strong> \"III\"</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> num = 4\n",
    "<strong>输出:</strong> \"IV\"</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> num = 9\n",
    "<strong>输出:</strong> \"IX\"</pre>\n",
    "\n",
    "<p><strong>示例 4:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> num = 58\n",
    "<strong>输出:</strong> \"LVIII\"\n",
    "<strong>解释:</strong> L = 50, V = 5, III = 3.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> num = 1994\n",
    "<strong>输出:</strong> \"MCMXCIV\"\n",
    "<strong>解释:</strong> M = 1000, CM = 900, XC = 90, IV = 4.</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= num <= 3999</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [integer-to-roman](https://leetcode.cn/problems/integer-to-roman/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [integer-to-roman](https://leetcode.cn/problems/integer-to-roman/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '58', '1994']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        digits = [(1000, \"M\"), (900, \"CM\"), (500, \"D\"), (400, \"CD\"), (100, \"C\"), \n",
    "                  (90, \"XC\"), (50, \"L\"), (40, \"XL\"), (10, \"X\"), (9, \"IX\"), \n",
    "                  (5, \"V\"), (4, \"IV\"), (1, \"I\")]\n",
    "        \n",
    "        roman_digits = []\n",
    "        # Loop through each symbol.\n",
    "        for value, symbol in digits:\n",
    "            # We don't want to continue looping if we're done.\n",
    "            if num == 0: break\n",
    "            count, num = divmod(num, value)\n",
    "            # Append \"count\" copies of \"symbol\" to roman_digits.\n",
    "            roman_digits.append(symbol * count)\n",
    "        return \"\".join(roman_digits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if num <1 or num > 3999:\n",
    "            return ''\n",
    "        d=[['I','II','III','IV','V','VI','VII','VIII','IX'],['X','XX','XXX','XL','L','LX','LXX','LXXX','XC'],['C','CC','CCC','CD','D','DC','DCC','DCCC','CM'],['M','MM','MMM']]\n",
    "        print(d)\n",
    "        str_num=''\n",
    "        th = int(num/1000)\n",
    "        if th:\n",
    "            str_num +=d[3][th-1]\n",
    "        h = (int(num/100))%10\n",
    "        if h:\n",
    "            str_num += d[2][h-1]\n",
    "        t = (int(num/10))%10\n",
    "        if t:\n",
    "            str_num += d[1][t-1]\n",
    "        x = num%10\n",
    "        if x:\n",
    "            str_num += d[0][x-1]\n",
    "        return str_num\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        m = ['','M','MM','MMM']\n",
    "        c = ['','C','CC','CCC','CD','D','DC','DCC','DCCC','CM']\n",
    "        l = ['','X','XX','XXX','XL','L','LX','LXX','LXXX','XC']\n",
    "        x = ['','I','II','III','IV','V','VI','VII','VIII','IX']\n",
    "\n",
    "        m1, m2 = num//1000, num%1000\n",
    "        c1, c2 = m2//100, m2%100\n",
    "        l1, l2 = c2//10, c2%10\n",
    "\n",
    "        r_num = m[m1] + c[c1] + l[l1] + x[l2]\n",
    "\n",
    "        return (r_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: 'int') -> 'str':\n",
    "        nums = [(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'), (100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'), (10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')]\n",
    "        ret = ''\n",
    "        i = 0\n",
    "        while num:\n",
    "            v, s = nums[i]\n",
    "            if num >= v:\n",
    "                num -= v\n",
    "                ret += s\n",
    "            else:\n",
    "                i += 1\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\r\n",
    "# @lc app=leetcode.cn id=12 lang=python3\r\n",
    "#\r\n",
    "# [12] 整数转罗马数字\r\n",
    "#\r\n",
    "# https://leetcode-cn.com/problems/integer-to-roman/description/\r\n",
    "#\r\n",
    "# algorithms\r\n",
    "# Medium (57.10%)\r\n",
    "# Total Accepted:    14.7K\r\n",
    "# Total Submissions: 25.8K\r\n",
    "# Testcase Example:  '3'\r\n",
    "#\r\n",
    "# 罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。\r\n",
    "# \r\n",
    "# 字符          数值\r\n",
    "# I             1\r\n",
    "# V             5\r\n",
    "# X             10\r\n",
    "# L             50\r\n",
    "# C             100\r\n",
    "# D             500\r\n",
    "# M             1000\r\n",
    "# \r\n",
    "# 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V +\r\n",
    "# II 。\r\n",
    "# \r\n",
    "# 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5\r\n",
    "# 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：\r\n",
    "# \r\n",
    "# \r\n",
    "# I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。\r\n",
    "# X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 \r\n",
    "# C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。\r\n",
    "# \r\n",
    "# \r\n",
    "# 给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。\r\n",
    "# \r\n",
    "# 示例 1:\r\n",
    "# \r\n",
    "# 输入: 3\r\n",
    "# 输出: \"III\"\r\n",
    "# \r\n",
    "# 示例 2:\r\n",
    "# \r\n",
    "# 输入: 4\r\n",
    "# 输出: \"IV\"\r\n",
    "# \r\n",
    "# 示例 3:\r\n",
    "# \r\n",
    "# 输入: 9\r\n",
    "# 输出: \"IX\"\r\n",
    "# \r\n",
    "# 示例 4:\r\n",
    "# \r\n",
    "# 输入: 58\r\n",
    "# 输出: \"LVIII\"\r\n",
    "# 解释: L = 50, V = 5, III = 3.\r\n",
    "# \r\n",
    "# \r\n",
    "# 示例 5:\r\n",
    "# \r\n",
    "# 输入: 1994\r\n",
    "# 输出: \"MCMXCIV\"\r\n",
    "# 解释: M = 1000, CM = 900, XC = 90, IV = 4.\r\n",
    "# \r\n",
    "#\r\n",
    "class Solution:\r\n",
    "    def intToRoman(self, num: 'int') -> 'str':\r\n",
    "        t = tuple(\r\n",
    "            zip(\r\n",
    "                [1000, 900, 500, 400, 100,   90,  50,    40, 10,  9,   5,     4, 1 ],\r\n",
    "                ['M', 'CM', 'D', 'CD', 'C', 'XC',  'L', 'XL','X','IX', 'V', 'IV', 'I' ]\r\n",
    "            )\r\n",
    "        )\r\n",
    "\r\n",
    "        ret = ''\r\n",
    "        for one in t:\r\n",
    "            while num >= one[0]:\r\n",
    "                num -= one[0]\r\n",
    "                ret += one[1]\r\n",
    "\r\n",
    "        return ret\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "roman_list = [(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'), (100, 'C'), (90, 'XC'),\n",
    "              (50, 'L'), (40, 'XL'), (10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')]\n",
    "class Solution:\n",
    "    def intToRoman(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        s = ''\n",
    "        for key, value in roman_list:\n",
    "            while num >= key:\n",
    "                s += value\n",
    "                num -= key\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.base = {\n",
    "            0:'',1:'I',2:'II',3:'III',4:'IV',5:'V',6:'VI',7:'VII',8:'VIII',9:'IX',10:'X',\n",
    "            20:'XX',30:'XXX',40:'XL',50:'L',60:'LX',70:'LXX',80:'LXXX',90:'XC',100:'C',\n",
    "            200:'CC',300:'CCC',400:'CD',500:'D',600:'DC',700:'DCC',800:'DCCC',900:'CM',1000:'M'\n",
    "        }\n",
    "    \n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        l = []\n",
    "        for i in [1000,100,10,1]:\n",
    "            a = (num//i)*i\n",
    "            l.append(a)\n",
    "            num -= a\n",
    "     \n",
    "        out = ''\n",
    "        if l[0]>=1000:\n",
    "            out += ''.join(self.base[1000]*(l[0]//1000)) \n",
    "        for i in l[1::]:\n",
    "            out += ''.join(self.base[i])             \n",
    "        return out\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        result = ''\n",
    "        div = [1, 5, 10, 50, 100, 500, 1000]\n",
    "        signs = ['I', 'V', 'X', 'L', 'C', 'D', 'M']\n",
    "        n = 2  #n和m用于按顺序不断生成1和2的数值\n",
    "        m = -1\n",
    "        for i in range(len(div) - 1, -1, -1):\n",
    "            a = num // div[i]\n",
    "            for j in range(a):\n",
    "                result += signs[i]\n",
    "            num -= div[i] * a\n",
    "            if i - n > -1 and num >= div[i] - div[i - n]:\n",
    "                result += signs[i - n] + signs[i]\n",
    "                num -= div[i] - div[i - n]\n",
    "            n += m\n",
    "            m *= -1\n",
    "            print(n)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        # 设立对应字典\n",
    "        d = {0:\"\", 1:\"I\", 5:\"V\", 10:\"X\", 50:\"L\", 100:\"C\", 500:\"D\", 1000:\"M\"}\n",
    "        # 输出值\n",
    "        value = \"\"\n",
    "        # 只要出现4后者9就需要特殊处理\n",
    "        # 记录当前位数\n",
    "        i = 0\n",
    "        while num:\n",
    "            extra = num%10\n",
    "            num = num//10\n",
    "            print(extra)\n",
    "            if extra == 4 or extra == 9:\n",
    "                right = 10 ** i * (extra+1)\n",
    "                left = 10 ** i\n",
    "                value = d[left] + d[right] + value\n",
    "            else:\n",
    "                left = 10 ** i * (extra//5) * 5\n",
    "                right = 10 ** i\n",
    "                value = d[left] + d[right] * (extra%5) + value\n",
    "            i += 1\n",
    "        \n",
    "        return value\n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        roman = defaultdict(str)\n",
    "        flag = 0\n",
    "        for x in range(11,44):\n",
    "            if x < 14:\n",
    "                roman[str(x)] = 'I'*(x-10)\n",
    "            elif x == 14:\n",
    "                roman[str(x)] = 'IV'\n",
    "            elif x < 19:\n",
    "                roman[str(x)] = 'V'+'I'*(x-15)\n",
    "            elif x == 19:\n",
    "                roman[str(x)] = 'IX'\n",
    "            elif x < 24:\n",
    "                roman[str(x)] = 'X'*(x-20)\n",
    "            elif x == 24:\n",
    "                roman[str(x)] = 'XL'\n",
    "            elif 24 < x < 29:\n",
    "                roman[str(x)] = 'L'+'X'*(x-25)\n",
    "            elif x == 29:\n",
    "                roman[str(x)] = 'XC'\n",
    "            elif x < 34:\n",
    "                roman[str(x)] = 'C'*(x-30)\n",
    "            elif x == 34:\n",
    "                roman[str(x)] = 'CD'\n",
    "            elif x < 39:\n",
    "                roman[str(x)] = 'D'+'C'*(x-35)\n",
    "            elif x == 39:\n",
    "                roman[str(x)] = 'CM'\n",
    "            elif x < 44:\n",
    "                roman[str(x)] = 'M'*(x-40)\n",
    "        rstr = ''\n",
    "        while num > 0:\n",
    "            flag += 1\n",
    "            numstr = str(flag) + str(num % 10)\n",
    "            num //= 10\n",
    "            print(numstr)\n",
    "            rstr = roman[numstr] + rstr\n",
    "        return rstr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        result=\"\"\n",
    "        lst=[[\"M\"],[\"C\",\"D\"],[\"X\",\"L\"],[\"I\",\"V\"]]\n",
    "        n=0\n",
    "        s=num//1000\n",
    "        r=num%1000\n",
    "        while n<4:\n",
    "            if s<5:\n",
    "                if s==4:\n",
    "                    result+=lst[n][0]+lst[n][1]\n",
    "                else:\n",
    "                    result+=lst[n][0]*s\n",
    "            else:\n",
    "                if s==9:\n",
    "                    result+=lst[n][0]+lst[n-1][0]\n",
    "                else:\n",
    "                    result+=lst[n][1]+lst[n][0]*(s-5)\n",
    "            n+=1\n",
    "            s=r//10**(3-n)\n",
    "            r=r%10**(3-n)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        li = [['I',\"V\"],['X','L'],['C','D'],['M']]\n",
    "        res = ''\n",
    "        k = 0\n",
    "        while num > 0:\n",
    "            last_num = num % 10\n",
    "            num //= 10\n",
    "            if last_num == 4:\n",
    "                add = li[k][0] + li[k][1]\n",
    "            elif last_num == 9:\n",
    "                add = li[k][0] + li[k+1][0]\n",
    "            elif last_num == 0:\n",
    "                k += 1\n",
    "                continue\n",
    "            elif last_num < 4:\n",
    "                add = last_num * li[k][0]\n",
    "            else:\n",
    "                add = li[k][1] + (last_num - 5) * li[k][0]\n",
    "            res = add + res\n",
    "            k += 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        \n",
    "        yushu = 0\n",
    "        luoma_dict = {1:'I', 5:'V', 10:'X', 50:'L', 100:'C', 500:'D', 1000:'M'}\n",
    "        chengshu = 1\n",
    "        s = ''\n",
    "        while num != 0:\n",
    "            yushu = num % 10\n",
    "            if yushu == 4 or yushu == 9:\n",
    "                s = luoma_dict[chengshu] + luoma_dict[(yushu+1) * chengshu] + s\n",
    "            elif yushu < 5:\n",
    "                s = luoma_dict[chengshu] * (yushu % 5) + s\n",
    "            else:\n",
    "                s = luoma_dict[5 * chengshu] + luoma_dict[chengshu] * (yushu % 5) + s\n",
    "             \n",
    "            num //= 10\n",
    "            chengshu *= 10\n",
    "        return s\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        nums = (1000, 500, 100, 50, 10, 5, 1)\n",
    "        syms = (\"M\", \"D\", \"C\", \"L\", \"X\", \"V\", \"I\")\n",
    "        d = {num: sym  for num, sym in zip(nums, syms)}\n",
    "        s=\"\"\n",
    "        if num<=0 or num>=4000:\n",
    "            raise ValueError(\"数字不在[1,3999]内\")\n",
    "        for i in range(len(nums)):\n",
    "            div_res,num=divmod(num,nums[i])\n",
    "            if div_res:\n",
    "                if div_res==4:\n",
    "                    s+=d[nums[i]]+d[nums[i-1]]\n",
    "                elif div_res==1 and i!=len(nums)-1 and num//nums[i+1]==4:\n",
    "                    s+=d[nums[i+1]]+d[nums[i-1]]\n",
    "                    num=num%nums[i+1]\n",
    "                else:\n",
    "                    s+=div_res*d[nums[i]]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef intToRoman(self, num: 'int') -> 'str':\n",
    "\t\tres = ''\n",
    "\t\t# M\n",
    "\t\tN1 = int(num / 1000)\n",
    "\t\tres = res + 'M' * N1\n",
    "\t\t\n",
    "\t\t# C\n",
    "\t\ttemp = ['','C','CC','CCC','CD','D','DC','DCC','DCCC','CM']\n",
    "\t\tN2 = int(num % 1000 / 100)\n",
    "\t\tres = res + temp[N2]\n",
    "\t\t\n",
    "\t\t# X\n",
    "\t\ttemp = ['','X','XX','XXX','XL','L','LX','LXX','LXXX','XC']\n",
    "\t\tN3 = int(num % 100 / 10)\n",
    "\t\tres = res + temp[N3]\n",
    "\n",
    "\t\t# I\n",
    "\t\ttemp = ['','I','II','III','IV','V','VI','VII','VIII','IX']\n",
    "\t\tN4 = int(num % 10)\n",
    "\t\tres = res + temp[N4]\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        strs = [\"I\", \"V\", \"X\", \"L\", \"C\", \"D\", \"M\"]\n",
    "        step = 0\n",
    "        total = ''\n",
    "        while num:\n",
    "            num, val = divmod(num, 10)\n",
    "            tmp = ''\n",
    "            if val >= 5:\n",
    "                val -= 5\n",
    "                if val == 0:\n",
    "                    tmp = strs[step+1]\n",
    "                elif val == 4:\n",
    "                    tmp = strs[step] + strs[step+2]\n",
    "                else:\n",
    "                    tmp = strs[step+1] + strs[step]*val\n",
    "            else:\n",
    "                if val == 0:\n",
    "                    pass\n",
    "                elif val == 4:\n",
    "                    tmp = strs[step] + strs[step+1]\n",
    "                else:\n",
    "                    tmp = strs[step]*val\n",
    "            step += 2\n",
    "            total = tmp + total\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        ans=''\n",
    "        while num>=1000:\n",
    "            ans+='M'\n",
    "            num-=1000\n",
    "        if num>=900:\n",
    "            ans+='CM'\n",
    "            num-=900\n",
    "        else:\n",
    "            while num>=500:\n",
    "                ans+='D'\n",
    "                num-=500\n",
    "            if num>=400:\n",
    "                ans+='CD'\n",
    "                num-=400\n",
    "            else:\n",
    "                while num>=100:\n",
    "                    ans+='C'\n",
    "                    num-=100\n",
    "        if num>=90:\n",
    "            ans+='XC'\n",
    "            num-=90\n",
    "        else:\n",
    "            while num>=50:\n",
    "                ans+='L'\n",
    "                num-=50\n",
    "            if num>=40:\n",
    "                ans+='XL'\n",
    "                num-=40\n",
    "            else:\n",
    "                while num>=10:\n",
    "                    ans+='X'\n",
    "                    num-=10\n",
    "        if num>=9:\n",
    "            ans+='IX'\n",
    "            num-=9\n",
    "        else:\n",
    "            while num>=5:\n",
    "                ans+='V'\n",
    "                num-=5\n",
    "            if num>=4:\n",
    "                ans+='IV'\n",
    "                num-=4\n",
    "            else:\n",
    "                while num>=1:\n",
    "                    ans+='I'\n",
    "                    num-=1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        rome ={\n",
    "            1:'I',\n",
    "            4:'IV',\n",
    "            5:'V',\n",
    "            9:'IX',\n",
    "            10:'X',\n",
    "            40:'XL',\n",
    "            50:'L',\n",
    "            90:'XC',\n",
    "            100:'C',\n",
    "            400:'CD',\n",
    "            500:'D',\n",
    "            900:'CM',\n",
    "            1000:'M',\n",
    "        }\n",
    "        compare = [1000,900,500,400,100,90,50,40,10,9,5,4,1]\n",
    "        ans =\"\"\n",
    "        i=0\n",
    "        while num!=0:\n",
    "            while num >= compare[i]:\n",
    "                ans += rome[compare[i]]\n",
    "                num -=compare[i]\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        dic_roma = {1:'I',5:'V',10:'X',50:'L',100:'C',500:'D',1000:'M'}\n",
    "        dic_left = {4:'I',9:'I',40:'X',90:'X',400:'C',900:'C'}\n",
    "        str_roma = []\n",
    "        i = len(str(num))\n",
    "        while i > 0:\n",
    "            if i == 4:\n",
    "                str_roma.append(num//1000 * dic_roma[1000])\n",
    "                num = num % 1000\n",
    "            if i == 3:\n",
    "                num_tmp = num - num % 100\n",
    "                if num_tmp == 400 or num_tmp == 900:\n",
    "                    str_roma.append(dic_left[num_tmp])\n",
    "                    str_roma.append(dic_roma[num_tmp + 100])\n",
    "                elif num_tmp >= 500:\n",
    "                    num_tmp0 = 500\n",
    "                    num_tmp1 = (num_tmp - num_tmp0) // 100 * dic_roma[100]\n",
    "                    str_roma.append(dic_roma[num_tmp0])\n",
    "                    str_roma.append(num_tmp1)\n",
    "                else:\n",
    "                    num_tmp1 = num_tmp // 100 * dic_roma[100]\n",
    "                    str_roma.append(num_tmp1)\n",
    "                num = num % 100    \n",
    "                \n",
    "            if  i == 2:\n",
    "                num_tmp = num - num % 10\n",
    "                if num_tmp == 40 or num_tmp == 90:\n",
    "                    str_roma.append(dic_left[num_tmp])\n",
    "                    str_roma.append(dic_roma[num_tmp + 10])\n",
    "                elif num_tmp >= 50:\n",
    "                    num_tmp0 = 50\n",
    "                    num_tmp1 = (num_tmp - num_tmp0) // 10 * dic_roma[10]\n",
    "                    str_roma.append(dic_roma[num_tmp0])\n",
    "                    str_roma.append(num_tmp1)\n",
    "                else:\n",
    "                    num_tmp1 = num_tmp // 10 * dic_roma[10]\n",
    "                    str_roma.append(num_tmp1)\n",
    "                num = num % 10\n",
    "            if i == 1:\n",
    "                num_tmp = num\n",
    "                if num_tmp == 4 or num_tmp == 9:\n",
    "                    str_roma.append(dic_left[num_tmp])\n",
    "                    str_roma.append(dic_roma[num_tmp + 1])\n",
    "                elif num_tmp >= 5:\n",
    "                    num_tmp0 = 5\n",
    "                    num_tmp1 = (num_tmp - num_tmp0) * dic_roma[1]\n",
    "                    str_roma.append(dic_roma[num_tmp0])\n",
    "                    str_roma.append(num_tmp1)\n",
    "                else:\n",
    "                    num_tmp1 = num_tmp  * dic_roma[1]\n",
    "                    str_roma.append(num_tmp1)\n",
    "            i -= 1\n",
    "        print(str_roma)\n",
    "        return ''.join(str_roma)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        hashmap={1000:'M',900:'CM',500:'D',400:'CD',100:'C',90:'XC',50:'L',40:'XL',10:'X',9:'IX',5:'V',4:'IV',1:'I'}\n",
    "        res=''\n",
    "        for key in hashmap:\n",
    "            if num//key!=0:\n",
    "                count=num//key\n",
    "                res+=hashmap[key]*count\n",
    "                num%=key\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        list1=[1000,900,500,400,100,90,50,40,10,9,5,4,1]\n",
    "        list2=['M','CM','D','CD','C','XC','L','XL','X','IX','V','IV','I']\n",
    "        result=\"\"\n",
    "        for i in range(len(list1)):\n",
    "            while num>=list1[i]:\n",
    "                result+=list2[i]\n",
    "                num-=list1[i]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        m = [\n",
    "            ['', 'M', 'MM', 'MMM'],\n",
    "            ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM'],\n",
    "            ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'],\n",
    "            ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX']\n",
    "        ]\n",
    "\n",
    "        n = [1000, 100, 10, 1]\n",
    "        r = ''\n",
    "        for i, e in enumerate(n):\n",
    "            r += m[i][(num // e)]\n",
    "            num = num % e\n",
    "\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def intToRoman(self, num: int) -> str:\r\n",
    "        str_num=str(num)\r\n",
    "        len_num=len(str_num)\r\n",
    "        s=''\r\n",
    "        hundred_dict={\r\n",
    "            '0':'',\r\n",
    "            '1':'C',\r\n",
    "            '2':'CC',\r\n",
    "            '3':'CCC',\r\n",
    "            '4':'CD',\r\n",
    "            '5':'D',\r\n",
    "            '6':'DC',\r\n",
    "            '7':'DCC',\r\n",
    "            '8':'DCCC',\r\n",
    "            '9':'CM'\r\n",
    "        }\r\n",
    "        ten_dict={\r\n",
    "            '0':'',\r\n",
    "            '1':'X',\r\n",
    "            '2':'XX',\r\n",
    "            '3':'XXX',\r\n",
    "            '4':'XL',\r\n",
    "            '5':'L',\r\n",
    "            '6':'LX',\r\n",
    "            '7':'LXX',\r\n",
    "            '8':'LXXX',\r\n",
    "            '9':'XC'\r\n",
    "        }\r\n",
    "        unit_dict={\r\n",
    "            '0':'',\r\n",
    "            '1':'I',\r\n",
    "            '2':'II',\r\n",
    "            '3':'III',\r\n",
    "            '4':'IV',\r\n",
    "            '5':'V',\r\n",
    "            '6':'VI',\r\n",
    "            '7':'VII',\r\n",
    "            '8':'VIII',\r\n",
    "            '9':'IX'\r\n",
    "        }\r\n",
    "        for i in str_num:\r\n",
    "            if len_num==4:\r\n",
    "                s=s+('M'*int(i))\r\n",
    "            elif len_num==3:\r\n",
    "                s=s+(hundred_dict.get(i))\r\n",
    "            elif len_num==2:\r\n",
    "                s=s+(ten_dict.get(i))\r\n",
    "            else:\r\n",
    "                s=s+(unit_dict.get(i))\r\n",
    "            print(s)\r\n",
    "            len_num-=1\r\n",
    "        return s\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        s=str(num)\n",
    "        if num<4:\n",
    "            return 'I'*num\n",
    "        elif num==4:\n",
    "            return 'IV'\n",
    "        elif num<9:\n",
    "            return 'V'+'I'*(num-5)\n",
    "        elif num==9:\n",
    "            return 'IX'\n",
    "        #<39\n",
    "        elif num<40:\n",
    "            if s[1]=='4':\n",
    "                return 'X'*(num//10)+'IV'\n",
    "            elif s[1]=='9':\n",
    "                return 'X'*(num//10)+'IX'\n",
    "            elif int(s[1])<4:\n",
    "                return 'X'*(num//10)+'I'*(int(s[1]))\n",
    "            elif int(s[1])<9:\n",
    "                return 'X'*(num//10)+'V'+'I'*(int(s[1])-5)\n",
    "        #40-49\n",
    "        elif num<50:\n",
    "            if s[1]=='4':\n",
    "                return 'XL'+'IV'\n",
    "            elif s[1]=='9':\n",
    "                return 'XL'+'IX'\n",
    "            elif int(s[1])<4:\n",
    "                return 'XL'+'I'*(int(s[1]))\n",
    "            elif int(s[1])<9:\n",
    "                return 'XL'+'V'+'I'*(int(s[1])-5)\n",
    "        #50-89\n",
    "        elif num<90:\n",
    "            if s[1]=='4':\n",
    "                return 'L'+'X'*((num-50)//10)+'IV'\n",
    "            elif s[1]=='9':\n",
    "                return 'L'+'X'*((num-50)//10)+'IX'\n",
    "            elif int(s[1])<4:\n",
    "                return 'L'+'X'*((num-50)//10)+'I'*(int(s[1]))\n",
    "            elif int(s[1])<9:\n",
    "                return 'L'+'X'*((num-50)//10)+'V'+'I'*(int(s[1])-5)\n",
    "        #90-99\n",
    "        elif num<100:\n",
    "            if s[1]=='4':\n",
    "                return 'XC'+'IV'\n",
    "            elif s[1]=='9':\n",
    "                return 'XC'+'IX'\n",
    "            elif int(s[1])<4:\n",
    "                return 'XC'+'I'*(int(s[1]))\n",
    "            elif int(s[1])<9:\n",
    "                return 'XC'+'V'+'I'*(int(s[1])-5)\n",
    "        #100-399\n",
    "        elif num<400:\n",
    "            if s[1]=='4':\n",
    "                if s[2]=='4':\n",
    "                    return 'C'*(num//100)+'XL'+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'C'*(num//100)+'XL'+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'C'*(num//100)+'XL'+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'C'*(num//100)+'XL'+'V'+'I'*(int(s[2])-5)\n",
    "            elif s[1]=='9':\n",
    "                if s[2]=='4':\n",
    "                    return 'C'*(num//100)+'XC'+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'C'*(num//100)+'XC'+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'C'*(num//100)+'XC'+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'C'*(num//100)+'XC'+'V'+'I'*(int(s[2])-5)\n",
    "            elif int(s[1])<4:\n",
    "                if s[2]=='4':\n",
    "                    return 'C'*(num//100)+'X'*(int(s[1]))+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'C'*(num//100)+'X'*(int(s[1]))+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'C'*(num//100)+'X'*(int(s[1]))+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'C'*(num//100)+'X'*(int(s[1]))+'V'+'I'*(int(s[2])-5)    \n",
    "            else:\n",
    "                if s[2]=='4':\n",
    "                    return 'C'*(num//100)+'L'+'X'*(int(s[1])-5)+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'C'*(num//100)+'L'+'X'*(int(s[1])-5)+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'C'*(num//100)+'L'+'X'*(int(s[1])-5)+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'C'*(num//100)+'L'+'X'*(int(s[1])-5)+'V'+'I'*(int(s[2])-5)\n",
    "        #400-499\n",
    "        elif num<500:\n",
    "            if s[1]=='4':\n",
    "                if s[2]=='4':\n",
    "                    return 'CD'+'XL'+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'CD'+'XL'+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'CD'+'XL'+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'CD'+'XL'+'V'+'I'*(int(s[2])-5)\n",
    "            elif s[1]=='9':\n",
    "                if s[2]=='4':\n",
    "                    return 'CD'+'XC'+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'CD'+'XC'+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'CD'+'XC'+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'CD'+'XC'+'V'+'I'*(int(s[2])-5)\n",
    "            elif int(s[1])<4:\n",
    "                if s[2]=='4':\n",
    "                    return 'CD'+'X'*(int(s[1]))+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'CD'+'X'*(int(s[1]))+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'CD'+'X'*(int(s[1]))+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'CD'+'X'*(int(s[1]))+'V'+'I'*(int(s[2])-5)    \n",
    "            else:\n",
    "                if s[2]=='4':\n",
    "                    return 'CD'+'L'+'X'*(int(s[1])-5)+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'CD'+'L'+'X'*(int(s[1])-5)+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'CD'+'L'+'X'*(int(s[1])-5)+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'CD'+'L'+'X'*(int(s[1])-5)+'V'+'I'*(int(s[2])-5)\n",
    "        # 500-899\n",
    "        elif num<900:\n",
    "            if s[1]=='4':\n",
    "                if s[2]=='4':\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'XL'+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'XL'+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'XL'+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'XL'+'V'+'I'*(int(s[2])-5)\n",
    "            elif s[1]=='9':\n",
    "                if s[2]=='4':\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'XC'+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'XC'+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'XC'+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'XC'+'V'+'I'*(int(s[2])-5)\n",
    "            elif int(s[1])<4:\n",
    "                if s[2]=='4':\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'X'*(int(s[1]))+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'X'*(int(s[1]))+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'X'*(int(s[1]))+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'X'*(int(s[1]))+'V'+'I'*(int(s[2])-5)    \n",
    "            else:\n",
    "                if s[2]=='4':\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'L'+'X'*(int(s[1])-5)+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'L'+'X'*(int(s[1])-5)+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'L'+'X'*(int(s[1])-5)+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'D'*(num//500)+'C'*((num-500)//100)+'L'+'X'*(int(s[1])-5)+'V'+'I'*(int(s[2])-5)\n",
    "        # 900-999                    \n",
    "        elif num<1000:\n",
    "            if s[1]=='4':\n",
    "                if s[2]=='4':\n",
    "                    return 'CM'+'XL'+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'CM'+'XL'+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'CM'+'XL'+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'CM'+'XL'+'V'+'I'*(int(s[2])-5)\n",
    "            elif s[1]=='9':\n",
    "                if s[2]=='4':\n",
    "                    return 'CM'+'XC'+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'CM'+'XC'+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'CM'+'XC'+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'CM'+'XC'+'V'+'I'*(int(s[2])-5)\n",
    "            elif int(s[1])<4:\n",
    "                if s[2]=='4':\n",
    "                    return 'CM'+'X'*(int(s[1]))+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'CM'+'X'*(int(s[1]))+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'CM'+'X'*(int(s[1]))+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'CM'+'X'*(int(s[1]))+'V'+'I'*(int(s[2])-5)    \n",
    "            else:\n",
    "                if s[2]=='4':\n",
    "                    return 'CM'+'L'+'X'*(int(s[1])-5)+'IV'\n",
    "                elif s[2]=='9':\n",
    "                    return 'CM'+'L'+'X'*(int(s[1])-5)+'IX'\n",
    "                elif int(s[2])<4:\n",
    "                    return 'CM'+'L'+'X'*(int(s[1])-5)+'I'*int(s[2])\n",
    "                else:\n",
    "                    return 'CM'+'L'+'X'*(int(s[1])-5)+'V'+'I'*(int(s[2])-5)                \n",
    "        #1000-3999\n",
    "        else:\n",
    "            if s[1]=='4':\n",
    "                if s[2]=='4':\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'CD'+'XL'+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'CD'+'XL'+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'CD'+'XL'+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'CD'+'XL'+'V'+'I'*(int(s[3])-5)\n",
    "                elif s[2]=='9':\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'CD'+'XC'+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'CD'+'XC'+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'CD'+'XC'+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'CD'+'XC'+'V'+'I'*(int(s[3])-5)\n",
    "                elif int(s[2])<4:\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'CD'+'X'*(int(s[2]))+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'CD'+'X'*(int(s[2]))+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'CD'+'X'*(int(s[2]))+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'CD'+'X'*(int(s[2]))+'V'+'I'*(int(s[3])-5)    \n",
    "                else:\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'CD'+'L'+'X'*(int(s[2])-5)+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'CD'+'L'+'X'*(int(s[2])-5)+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'CD'+'L'+'X'*(int(s[2])-5)+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'CD'+'L'+'X'*(int(s[2])-5)+'V'+'I'*(int(s[3])-5)     \n",
    "            elif s[1]=='9':\n",
    "                if s[2]=='4':\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'CM'+'XL'+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'CM'+'XL'+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'CM'+'XL'+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'CM'+'XL'+'V'+'I'*(int(s[3])-5)\n",
    "                elif s[2]=='9':\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'CM'+'XC'+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'CM'+'XC'+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'CM'+'XC'+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'CM'+'XC'+'V'+'I'*(int(s[3])-5)\n",
    "                elif int(s[2])<4:\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'CM'+'X'*(int(s[2]))+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'CM'+'X'*(int(s[2]))+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'CM'+'X'*(int(s[2]))+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'CM'+'X'*(int(s[2]))+'V'+'I'*(int(s[3])-5)    \n",
    "                else:\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'CM'+'L'+'X'*(int(s[2])-5)+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'CM'+'L'+'X'*(int(s[2])-5)+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'CM'+'L'+'X'*(int(s[2])-5)+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'CM'+'L'+'X'*(int(s[2])-5)+'V'+'I'*(int(s[3])-5)  \n",
    "            elif int(s[1])<4:\n",
    "                if s[2]=='4':\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'XL'+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'XL'+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'XL'+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'XL'+'V'+'I'*(int(s[3])-5)\n",
    "                elif s[2]=='9':\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'XC'+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'XC'+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'XC'+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'XC'+'V'+'I'*(int(s[3])-5)\n",
    "                elif int(s[2])<4:\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'X'*(int(s[2]))+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'X'*(int(s[2]))+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'X'*(int(s[2]))+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'X'*(int(s[2]))+'V'+'I'*(int(s[3])-5)    \n",
    "                else:\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'L'+'X'*(int(s[2])-5)+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'L'+'X'*(int(s[2])-5)+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'L'+'X'*(int(s[2])-5)+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'C'*(int(s[1]))+'L'+'X'*(int(s[2])-5)+'V'+'I'*(int(s[3])-5)  \n",
    "            else:\n",
    "                if s[2]=='4':\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'XL'+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'XL'+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'XL'+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'XL'+'V'+'I'*(int(s[3])-5)\n",
    "                elif s[2]=='9':\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'XC'+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'XC'+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'XC'+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'XC'+'V'+'I'*(int(s[3])-5)\n",
    "                elif int(s[2])<4:\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'X'*(int(s[2]))+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'X'*(int(s[2]))+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'X'*(int(s[2]))+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'X'*(int(s[2]))+'V'+'I'*(int(s[3])-5)    \n",
    "                else:\n",
    "                    if s[3]=='4':\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'L'+'X'*(int(s[2])-5)+'IV'\n",
    "                    if int(s[3])<4:\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'L'+'X'*(int(s[2])-5)+'I'*(int(s[3]))\n",
    "                    if int(s[3])==9:\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'L'+'X'*(int(s[2])-5)+'IX'\n",
    "                    else:\n",
    "                        return 'M'*(int(s[0]))+'D'+'C'*(int(s[1])-5)+'L'+'X'*(int(s[2])-5)+'V'+'I'*(int(s[3])-5)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]\n",
    "        romans = [\"M\", \"CM\", \"D\", \"CD\", \"C\", \"XC\", \"L\", \"XL\", \"X\", \"IX\", \"V\", \"IV\", \"I\"]\n",
    "        \n",
    "        i = 0\n",
    "        s = \"\"\n",
    "        while i < len(nums) and num!=0:\n",
    "            if num >= nums[i]:\n",
    "                for j in range(num//nums[i]):\n",
    "                    s += romans[i]\n",
    "                num = num % nums[i]\n",
    "                print(num, nums[i], i)\n",
    "            i += 1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        ans = \"\"\n",
    "        dic = {1: \"I\", 4: \"IV\", 5: \"V\", 9: \"IX\", 10: \"X\", 40: \"XL\", 50: \"L\", 90: \"XC\", 100: \"C\", 400: \"CD\", 500: \"D\", 900: \"CM\", 1000:\"M\"}\n",
    "        keys = sorted(dic.keys(), reverse = True)\n",
    "       \n",
    "        while num > 0:\n",
    "            left, right = 0, len(keys) - 1\n",
    "            while left + 1 < right:\n",
    "                mid = (left + right) // 2\n",
    "                print(left, right, mid)\n",
    "                if keys[mid] == num:\n",
    "                    ans += dic[num]\n",
    "                    num -= keys[mid]\n",
    "                    break\n",
    "                \n",
    "                elif keys[mid] > num:\n",
    "                    left = mid \n",
    "                elif keys[mid] < num:\n",
    "                    right = mid\n",
    "            \n",
    "            for i in [left, right]:\n",
    "                if keys[i] <= num:\n",
    "                    ans += dic[keys[i]]\n",
    "                    num -= keys[i]\n",
    "                    break\n",
    "        return ans\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        hashmap = {\n",
    "            1000:'M',\n",
    "            900:'CM',\n",
    "            500:'D',\n",
    "            400:'CD',\n",
    "            100:'C',\n",
    "            90:'XC',\n",
    "            50:'L',\n",
    "            40:'XL',\n",
    "            10:'X',\n",
    "            9:'IX',\n",
    "            5:'V',\n",
    "            4:'IV',\n",
    "            1:'I'\n",
    "        }\n",
    "\n",
    "        res = ''\n",
    "\n",
    "        for key in hashmap.keys():\n",
    "            if num >= key:\n",
    "                cnt = num // key\n",
    "                res = res + hashmap[key] * cnt \n",
    "                num = num % key \n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        hashmap = {1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I'}\n",
    "        rst = \"\"\n",
    "        for k in hashmap:\n",
    "            if num >= k:\n",
    "                cnt = num // k\n",
    "                rst += hashmap[k] * cnt\n",
    "                num %= k\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        romans = [(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'), (100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'), (10, 'X'), (9,'IX'),(5, 'V'), (4, 'IV'),(1, 'I')]\n",
    "\n",
    "        s = ''\n",
    "        for a in romans:\n",
    "            if num >= a[0]:\n",
    "                times = ((num-num%a[0]) // a[0])\n",
    "                s += a[1]*times\n",
    "                num -= times*a[0]\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    VALUE_SYMBOLS = [\n",
    "        (1000, \"M\"),\n",
    "        (900, \"CM\"),\n",
    "        (500, \"D\"),\n",
    "        (400, \"CD\"),\n",
    "        (100, \"C\"),\n",
    "        (90, \"XC\"),\n",
    "        (50, \"L\"),\n",
    "        (40, \"XL\"),\n",
    "        (10, \"X\"),\n",
    "        (9, \"IX\"),\n",
    "        (5, \"V\"),\n",
    "        (4, \"IV\"),\n",
    "        (1, \"I\"),\n",
    "    ]\n",
    "\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        roman = list()\n",
    "        for value, symbol in Solution.VALUE_SYMBOLS:\n",
    "            while num >= value:\n",
    "                num -= value\n",
    "                roman.append(symbol)\n",
    "            if num == 0:\n",
    "                break\n",
    "        return \"\".join(roman)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        #hash1={1:'I',4:'IV',5:'V',9:'IX',10:'X',40:'XL',50:'L',90:'XC',100:'C',400:'CD',500:'D',900:'CM',1000:'M'}\n",
    "        hash1={1000:'M',900:'CM',500:'D',400:'CD',100:'C',90:'XC',50:'L',40:'XL',10:'X',9:'IX',5:'V',4:'IV',1:'I'}\n",
    "        # if num in hash1:\n",
    "        #     return hash1[num]\n",
    "        # else:\n",
    "        res=[]\n",
    "        \n",
    "        \n",
    "        for n in hash1.keys():\n",
    "            if num //n>=1:\n",
    "                times = num//n\n",
    "                print(n,times)\n",
    "                num=num%n\n",
    "                if num!=0:\n",
    "                    res.append(hash1[n]*times)\n",
    "                else:\n",
    "                    res.append(hash1[n]*times)\n",
    "        return ''.join(res)\n",
    "        \n",
    "\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        n2c = SortedDict({1000:'M',\n",
    "                          900:'CM',\n",
    "                          500:'D',\n",
    "                          400:'CD',\n",
    "                          100:'C',\n",
    "                          90:'XC',\n",
    "                          50:'L',\n",
    "                          40:'XL',\n",
    "                          10:'X',\n",
    "                          9:'IX',\n",
    "                          5:'V',\n",
    "                          4:'IV',\n",
    "                          1:'I'})\n",
    "\n",
    "        res = ''\n",
    "        for n in reversed(n2c.keys()):\n",
    "            if num//n != 0:\n",
    "                count = num//n\n",
    "                res += (n2c[n]*count)\n",
    "\n",
    "                num = num%n\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        hashmap = {\n",
    "            1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV',\n",
    "            1:'I'}\n",
    "        res = ''\n",
    "        for key in hashmap:\n",
    "            if num//key != 0:\n",
    "                count = num // key \n",
    "                res += hashmap[key] * count\n",
    "                num %= key\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    VALUE_SYMBOLS = [\n",
    "        (1000, \"M\"),\n",
    "        (900, \"CM\"),\n",
    "        (500, \"D\"),\n",
    "        (400, \"CD\"),\n",
    "        (100, \"C\"),\n",
    "        (90, \"XC\"),\n",
    "        (50, \"L\"),\n",
    "        (40, \"XL\"),\n",
    "        (10, \"X\"),\n",
    "        (9, \"IX\"),\n",
    "        (5, \"V\"),\n",
    "        (4, \"IV\"),\n",
    "        (1, \"I\"),\n",
    "    ]\n",
    "\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        roman = list()\n",
    "        for value, symbol in Solution.VALUE_SYMBOLS:\n",
    "            while num >= value:\n",
    "                num -= value\n",
    "                roman.append(symbol)\n",
    "            if num == 0:\n",
    "                break\n",
    "        return \"\".join(roman)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intToRoman(self, num: int) -> str:\n",
    "        symbols=[\"M\",\"CM\",\"D\",\"CD\",\"C\",\"XC\",\"L\",\"XL\",\"X\",\"IX\",\"V\",\"IV\",\"I\"]\n",
    "        values=[1000,900,500,400,100,90,50,40,10,9,5,4,1]\n",
    "\n",
    "        roman=\"\"\n",
    "\n",
    "        for i in range(len(symbols)):\n",
    "            while num>=values[i]:\n",
    "                roman+=symbols[i]\n",
    "                num-=values[i]\n",
    "\n",
    "\n",
    "        return roman\n",
    "\n",
    "\n",
    "solution=Solution()\n",
    "print(solution.intToRoman(3))\n",
    "print(solution.intToRoman(4))\n",
    "print(solution.intToRoman(9))\n",
    "print(solution.intToRoman(58))\n",
    "print(solution.intToRoman(1994))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
